#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "common.h"

#define SIZE 10

/*
low   5
heigh 4
midvalue = 53
O   1   2   3   4   5   6   7   8   9
53  71  21  69  23  57  68  39  29  79
29
                                71
    39




29  39  21  23  53  57  68  69  71  79
*/

static int partition(int arr[],int low,int high)
{
    int midvalue=arr[low];
    while (low<high)
    {
        //从高位找到小于中间值时结束，高位前移
        while(low<high && arr[high]>=midvalue)
            high--;
        //把高位中的小值换到低位 ，之后低位后移
        if(low<high)
            arr[low++]=arr[high];
        //从低位找到大于中间值时结束，低位后移
        while(low<high && arr[low]<=midvalue)
            low++;
        //把低位中的大值换到高位，之后高位前移
        if(low<high)
            arr[high--]=arr[low];
    }
    arr[low]=midvalue;
    return low;

}

void quicksort(int arr[],int low,int high)
{

    int pivotpos;
    if(low<high)
    {
        pivotpos=partition(arr,low,high);
        // printf("%d,%d,%d\n",low,pivotpos,high);
        // array_display(arr,SIZE,"排序中");
        quicksort(arr,low,pivotpos-1);
        quicksort(arr,pivotpos+1,high);
    }
}

int quictMain()
{
    int data[SIZE] = {53,71,21,69,23,87,68,39,29,79} ;
    // array_random(data,SIZE);
    array_display(data,SIZE,"原始数据");

    quicksort(data,0,SIZE - 1);

    array_display(data,SIZE,"排序结果");
    return 0;
}
